package leetcode.weekly.week333;

import java.util.HashMap;
import java.util.Map;

//Solution2Test
public class Solution2 {

	public int minOperations(int n) {
		Map<Integer, Integer> dp = new HashMap<>();
		return f(n, dp);
	}

	private int f(int n, Map<Integer, Integer> dp) {
		if (n == 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		if(dp.containsKey(n))
			return dp.get(n);
		int num = 1;
		int t = 0;
		while (num < n) {
			num <<= 1;
			t++;
		}
		if (num == n) {
			return 1;
		}
		int ans1 = f(n - (1 << (t - 1)),dp);
		int ans2 = f(num - n,dp);
		dp.put(n, Math.min(ans1, ans2) + 1);
		return dp.get(n);
	}

}
